Test Series - Data Structure

3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

Test Number 69/115

Q: Which type of binary search tree or algorithm does tango tree use?
A. Online
B. Offline
C. Static
D. Dynamic
Solution: Tango tree is an online binary search tree whose time complexity is O (log (log n)) when compared to the time complexity of offline binary search tree model. Online algorithm processes input or data provided piece by piece.
Q: What is the time complexity of for achieving competitive ratio by tango tree?
A. O (log n)
B. O (n2)
C. O (n!)
D. O (log (log n))
Solution: Tango tree is an online binary search tree whose time complexity is O (log (log n)) when compared to the time complexity of offline binary search tree model. Online algorithm processes input or data provided piece by piece.
Q: Which type of binary search tree is imitated for construction of tango tree?
A. Complete Binary Search Tree
B. Perfect Binary Search Tree
C. Balanced Binary Search Tree
D. Degenerate Binary Search Tree
Solution: Tango tree is constructed by simulating a complete binary search tree. This tree is also known as Reference tree, that contains all the elements of the tree. Also, the reference tree is never showed in actual implementation.
Q: Which special balanced binary search tree is used to store the nodes of auxiliary tree?
A. Red – Black Tree
B. Red – Brown Tree
C. Red – Yellow Tree
D. Red – Tango Tree
Solution: The path starting from the root and following the path of preferred child node till the end of leaf node is known as preferred path. Nodes are stored in Red – Black tree for the representation of the preferred path.
Q: Which operation is used to combine two auxiliary trees?
A. Join
B. Combinatorial
C. Add
D. Concatenation
Solution: If the top node of one of the reference tree amongst the two, is the is the child of the bottom node of the other reference tree, then the join operation can be carried out to join the two auxiliary trees.
Q: Which operation is used to break a preferred path into two sets of parts at a particular node?
A. Differentiate
B. Cut
C. Integrate
D. Join
Solution: A preferred path is broken into two parts. One of them is known as top part while other is known as bottom part. To break a preferred path into two sets, cut operation is used at a particular node.
Q: What is the upper bound for a tango tree if k is a number of interleaves?
A. k+2 O (log (log n))
B. k O (log n)
C. K2 O (log n)
D. k+1 O (log (log n))
Solution: Upper bound is found to analyze the work done by a tango tree on a given set of sequences. In order to connect to the tango tree, the upper bound is found to be k+1 O (log (log n)).
Q: What is the time complexity for searching k+1 auxiliary trees?
A. k+2 O (log (log n))
B. k+1 O (log n)
C. K+2 O (log n)
D. k+1 O (log (log n))
Solution: Since each search operation in the auxiliary tree takes O (log (log n)) time as auxiliary tree size is bounded by the height of the reference tree that is log n. So for k+1 auxiliary trees, total search time is k+1 O (log (log n)).
Q: What is the time complexity for the update cost on auxiliary trees?
A. O (log (log n))
B. k-1 O (log n)
C. K2 O (log n)
D. k+1 O (log (log n))
Solution: The update cost also is bounded by the upper bound. We perform one cut as well as one join operation for the auxiliary tree, so the total update cost for the auxiliary tree is found to be k+1 O (log (log n)).
Q: Which of the following is the self-adjusting binary search tree?
A. AVL Tree
B. Splay Tree
C. Top Tree
D. Ternary Tree
Solution: Splay tree is a self – adjusting binary search tree. It performs basic operations on the tree like insertion, deletion, loop up performing all these operations in O (log n) time.

You Have Score    /10